# 剑指 Offer II 119. 最长连续序列
# https://leetcode-cn.com/problems/WhsWhI/
#
# 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
# 示例 1：
# 输入：nums = [100,4,200,1,3,2]
# 输出：4
# 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
# 示例 2：
# 输入：nums = [0,3,7,2,5,8,4,6,0,1]
# 输出：9
# 提示：
#
# 0 <= nums.length <= 10^4
# -10^9 <= nums[i] <= 10^9
# 进阶：可以设计并实现时间复杂度为O(n) 的解决方案吗？
from queue import PriorityQueue
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        q_ = PriorityQueue()
        for num in nums:
            q_.put(num)
        if q_.empty():
            return 0

        size = 0
        tmp_size = 1
        tmp_num = q_.get()
        while not q_.empty():
            num = q_.get()
            if num > tmp_num + 1:
                if size < tmp_size:
                    size = tmp_size
                tmp_size = 1
            elif num == tmp_num + 1:
                tmp_size += 1
            tmp_num = num
        if size < tmp_size:
            size = tmp_size
        return size


solution = Solution()
assert solution.longestConsecutive([100, 4, 200, 1, 3, 2]) == 4
assert solution.longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
assert solution.longestConsecutive([0]) == 1
assert solution.longestConsecutive([]) == 0
assert solution.longestConsecutive([9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6]) == 7
